package com.projeto.desafio.calculos;

    

 
/**
 *
 * @author Maycon Olivatto
 * @version 1.0
 */
public class Dijkstra {
   
	// Dijkstra's algorithm to find shortest path from s to all other nodes
	public static int [] dijkstra (WeightedGraph wg, int s) {
		final int [] dist = new int [wg.size()];  // shortest known distance from "s"
		final int [] pred = new int [wg.size()];  // preceeding node in path
		final boolean [] visited = new boolean [wg.size()]; // all false initially

		for (int i=0; i<dist.length; i++) {
			dist[i] = Integer.MAX_VALUE;
		}
		dist[s] = 0;

		for (int i=0; i<dist.length; i++) {
			final int next = minVertex (dist, visited);
			visited[next] = true;

			// The shortest path to next is dist[next] and via pred[next].

			final int [] n = wg.neighbors (next);
			for (int j=0; j<n.length; j++) {
				final int v = n[j];
				final int d = dist[next] + wg.getWeight(next,v);
				if (dist[v] > d) {
					dist[v] = d;
					pred[v] = next;
				}
			}
		}
		return pred;  // (ignore pred[s]==0!)
	}

	private static int minVertex (int [] dist, boolean [] v) {
		int x = Integer.MAX_VALUE;
		int y = -1;   // graph not connected, or no unvisited vertices
		for (int i=0; i<dist.length; i++) {
			if (!v[i] && dist[i]<x) {
				y=i;
				x=dist[i];
			}
		}
		return y;
	}

	public static String printPath (WeightedGraph wg, int [] pred, int s, int e, float autonomia, float valor) {
		final java.util.ArrayList<Object> path = new java.util.ArrayList<Object>();
		int x = e;
		float total=0;
		while (x!=s) {
			path.add (0, wg.getLabel(x));	
			total += wg.getWeight(pred[x],x);
			System.out.println();
			x = pred[x];
		}
		total = (total/autonomia) * valor;
		
		path.add (0, wg.getLabel(s));
		return  ("Rota: "+path + " custo: R$"+total);
	}

}
